package leetcode_tag.回溯;

public class LeetCode10_n {
    public boolean isMatch1(String s, String p) {
        int n = s.length(), j = 0;
        char lastChar = ' ';
        for (int i = 0; i < n; i++) {
            char c1 = s.charAt(i);
            char c2 = p.charAt(j);
            if (c2 == '.')
                j++;
            else if (c2 == '*') {
                if (c1 != lastChar)
                    return false;
            } else if (c1 != c2)
                return false;
            lastChar = c1;
        }
        return true;
    }

    // 对于 .*这种特殊情况无法匹配
    public boolean isMatch2(String s, String p) {
        int pLength = p.length();
        int sLength = s.length();
        int j = 0;
        for (int i = 0; i < pLength; i++) {
            char c = p.charAt(i);
            if (c == '.')
                continue;
            else if (c == '*') {
                char tmp = s.charAt(j);
                while (j < sLength && s.charAt(j) == tmp)
                    j++;
            } else if (c != s.charAt(j))
                return false;
            else
                j++;
        }
        return j == sLength;
    }

    boolean result = false;

    public boolean isMatch(String s, String p) {
        int count = 0;
        for (char c : p.toCharArray()) {
            if (c != '*')
                count++;
        }
        helper(s, p, 0, s.length() - count, "");
        return result;
    }

    private void helper(String s, String p, int index, int lastSpace, String tmp) {
        System.out.println(tmp);
        if (result)
            return;
        if (lastSpace == 0) {
            int length = s.length();
            if (length != tmp.length())
                return;
            for (int i = 0; i < length; i++) {
                if (tmp.charAt(i) != '.' && tmp.charAt(i) != s.charAt(i))
                    return;
            }
            result = true;
            return;
        }
        if (index >= p.length())
            return;
        char c = p.charAt(index);
        if (c == '*') {
            helper(s, p, index, lastSpace - 1, tmp + tmp.charAt(tmp.length() - 1));
        } else
            helper(s, p, index + 1, lastSpace, tmp + c);
    }

    public static void main(String[] args) {
        LeetCode10_n leetCode10N = new LeetCode10_n();
        leetCode10N.helper("aa", "a*", 0, 1, "");
    }
}
